package a2022.a20221020;

/**
 * @author lenovo
 * @date 2022/10/20
 */
public class a {
    public static void main(String[] args) {
        System.out.println(kthGrammar(4, 6));
    }

    //     0   0
    //     1   01
    //     2   01 10
    //     3   01 10 10 01
    //     4   01 10 10 01 10 01 01 10
    public static int kthGrammar(int n, int k) {
        if (n < 3) {
            return k == 2 ? 1 : 0;
        }
        double num = 0;
        int i = 0;
        while (n >= 3) {
            num = Math.pow(2, (n - 1)) / 2;
            if (num < k) {
                k = (int) (k - num);
                i++;
            }
            n--;
        }
        return k == 2 ? i % 2 == 0 ? 1 : 0
                      : i % 2 == 0 ? 0 : 1;
    }


    public static int kthGrammar2(int n, int k) {
        return Integer.bitCount(k - 1) & 1;
    }
}
